package 单周赛.september;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @
 * @date 2024/06/16
 */
public class 第402场单周赛 {

    public static void main(String[] args) {

        System.out.println(maximumTotalDamage2(new int[]{1, 1, 3, 4}));

    }

    public int countCompleteDayPairs(int[] hours) {
        int cnt = 0;

        for (int i = 0; i < hours.length; i++) {

            for (int j = i + 1; j < hours.length; j++) {

                if ((hours[i] + hours[j]) % 24 == 0) {
                    cnt++;
                }

            }
        }
        return cnt;
    }

    /**
     * 对 24 取模
     */
    public long countCompleteDayPairs2(int[] hours) {
        long cnt = 0;
        int[] record = new int[24];
        for (int hour : hours) {
            record[hour % 24]++;
        }

        for (int r = 1; r <= record[12]; r++) {
            cnt += r - 1;
        }
        for (int r = 1; r <= record[0]; r++) {
            cnt += r - 1;
        }

        for (int r = 1; r <= 11; r++) {
            cnt += record[r] * record[24 - r];
        }
        return cnt;
    }

    private static long[] visit;

    private static long max = 0;

    /**
     * 排序+递归（超时）
     */
    public static long maximumTotalDamage(int[] power) {
        Arrays.sort(power);
        visit = new long[power.length];

        dfs(0, power, 0);

        return max;
    }

    private static void dfs(int i, int[] power, long sum) {
        if (visit[i] > sum) {
            return;
        }
        visit[i] = Math.max(visit[i], sum);

        if (i == power.length) {
            max = Math.max(max, sum);
            return;
        }
        if (i == power.length - 1) {
            max = Math.max(max, sum + power[i]);
            return;
        }

        int j = i + 1;
        long selectSum = power[i];
        while (j < power.length && power[j] == power[i]) {
            selectSum += power[i];
            j++;
        }

        // 不选
        dfs(j, power, sum);

        // 选
        while (j < power.length && power[j] - power[i] <= 2) {
            j++;
        }
        dfs(j, power, sum + selectSum);
    }

    /**
     * 一个魔法师有许多不同的咒语。
     * 给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。
     * 已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，
     * power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。
     * 每个咒语最多只能被使用 一次 。
     * 请你返回这个魔法师可以达到的伤害值之和的 最大值 。
     * ---
     * 动态规划+排序+二分查找
     * 1，排序不影响结果
     * 2，重复元素合并，要么都选，要么都不选
     * 3，动态规划
     * 选或不选
     * 选：dp[i] = dp[j] + power[i]  j 的索引位置是 [0,i-1] 中 < dp[i] - 2 的最大值
     * 不选：dp[i] = dp[i-1]
     * 注意 int 溢出！！！
     */
    public static long maximumTotalDamage2(int[] power) {
        Map<Long, Long> map = new HashMap<>();
        for (long num : power) {
            map.put(num, map.getOrDefault(num, 0L) + 1);
        }
        int idx = 0;
        long[] arr = new long[map.size()];
        for (Map.Entry<Long, Long> entry : map.entrySet()) {
            arr[idx] = entry.getKey();
            idx++;
        }
        Arrays.sort(arr);
        long[] dp = new long[arr.length];
        dp[0] = arr[0] * map.get(arr[0]);
        for (int i = 1; i < arr.length; i++) {

            // 返回 -1 表示找不到
            int j = binarySearch(arr, arr[i] - 2);

            if (j == -1) {
                dp[i] = Math.max(dp[i - 1], arr[i] * map.get(arr[i]));
            } else {
                dp[i] = Math.max(dp[i - 1], dp[j] + arr[i] * map.get(arr[i]));
            }
        }
        return dp[dp.length - 1];
    }

    // 找到 < target 的最大值索引
    private static int binarySearch(long[] power, long target) {
        int ans = -1;
        int left = 0, right = power.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (power[mid] < target) {
                ans = Math.max(ans, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }

}
